package com.datastructures.huffmancode;

import java.io.*;
import java.util.*;

/**
 * @author MaoLin Wang
 * @date 2019/11/820:12
 */
public class HuffmanCode {
    public static void main(String[] args) {

       /* String str = "i like like like java do you like a java";
        byte[] contentBytes = str.getBytes();
        byte[] bytes = huffmanZip(contentBytes);
        System.out.println(Arrays.toString(bytes));

        byte[] rawStr = decode(huffmanCodes, bytes);

        System.out.println(new String(rawStr));
*/

        //测试压缩文件
      //  String sourceFile = "D://PS素材/作品/新建文件夹/pexels-photo.png";
       // String decodeTarget="D:\\JAVA项目\\JSP\\JSP\\src\\com\\datastructures\\el\\s.java";
        String targetPath = "D:\\day24\\算法和数据结构\\资料\\压缩测试文件\\src.bmp";
        String targetPath2 = "D:\\day24\\算法和数据结构\\资料\\压缩测试文件\\src2.zip";
        zipFile(targetPath, targetPath2);
       // unzipFile(targetPath,targetPath2);
    }

    /**
     * @param zipFile        待解压的文件
     * @param targetFilePaeh 将文件解压到的路径
     */
    public static void unzipFile(String zipFile, String targetFilePaeh) {
        InputStream is = null;
        ObjectInputStream ois = null;
        OutputStream os = null;
        try {
            FileInputStream fis = new FileInputStream(zipFile);
            ois = new ObjectInputStream(fis);
            //读取byte数组 huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取哈夫曼编码表
            Map<Byte, String> codes = (Map<Byte, String>) ois.readObject();
            byte[] bytes = decode(codes, huffmanBytes);
//
            //将bytes写入到目标文件
            os = new FileOutputStream(targetFilePaeh);
            os.write(bytes);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {

            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }


    }

    /**
     * @param sourceFile 原文件全路径
     * @param dstFile    压缩后的文件目录
     */
    public static void zipFile(String sourceFile, String dstFile) {

        OutputStream os = null;
        ObjectOutputStream oos = null;
        FileInputStream fis = null;
        try {
            fis = new FileInputStream(sourceFile);
            //创建一个和源文件大小一样的byte[]
            byte[] b = new byte[fis.available()];
            //读取文件
            fis.read(b);

            //获取文件对应的哈夫曼编码表
            byte[] huffmanBytes = huffmanZip(b);
            //创建文件输出流，存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把哈夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //以对象流的方式写入哈夫曼编码。为了以后恢复源文件使用

            //一定要把哈夫曼编码写入压缩文件
            oos.writeObject(huffmanCodes);
        } catch (FileNotFoundException e) {
            System.out.println(e.getMessage());
        } catch (IOException e) {
            e.printStackTrace();
        } finally {

            try {
                oos.close();
                os.close();
                fis.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }





    /*
        数据解压：
        1.将[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
            重写转成哈夫曼编码对应的二进制的字符串
        2.二进制字符串转为原字符串
     */

    /**
     * @param huffmanCodes 护肤满编码表map
     * @param huffmanBytes 哈夫曼编码得到的字节数组
     * @return 原来的字符串对应的字节数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {

        //1.先得到huffmanBytes对应的二进制字符串
        StringBuilder stringBuilder = new StringBuilder();
        //将byte转成二进制字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);

            stringBuilder.append(bytes2String(!flag, huffmanBytes[i]));
        }
        System.out.println("哈夫曼字节数组转对应的二进制字符串:" + stringBuilder.toString());

        //把字符串按照指定的哈夫曼编码进行解码
        //把哈夫曼编码表进行调换，因为反向查询a->100 100 ->a
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        //使用集合存放byte
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;

            while (flag) {
                //1010100010111...
                //取出一个'1' '0'
                //i不动，count动，知道匹配到一个字符
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    //未匹配到
                    count++;
                } else {
                    //匹配到，退出循环
                    flag = false;
                }

            }
            list.add(b);
            i += count;
        }
        //把list中的数据放入到byte[]返回
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }

    /**
     * 将一个bye转成一个二进制字符串
     *
     * @param flag 如果是true，表示需要补高位，否则不补，如果是最后一个字节，不需要补高位
     * @param b    传入的byte
     * @return 改byte对应的二进制的字符串(按补码返回)
     */
    private static String bytes2String(boolean flag, byte b) {
        //使用变量保存b
        int temp = b;
        //如果是正数，还需要补高位
        if (flag) {

            temp |= 256;// 按位或 1 | 256-> 0000 0001 | 1 0000 0000 =>1 0000 0001
        }
        String str = Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码

        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    /**
     * @param bytes 原始的字符串对应的字节数组
     * @return 经过哈夫曼编码压缩后的数组
     */
    private static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        //创建哈夫曼树
        Node huffmanTree = createHuffmanTree(nodes);

        //对应的哈夫曼编码
        Map<Byte, String> codes = getCodes(huffmanTree);

        //根据生产的哈夫曼编码，压缩得到哈夫曼编码字节数组
        return zip(bytes, codes);
    }
    //将字符串对应的byte[] 数组，通过生成的哈夫曼编码表，返回一个哈夫曼编码压缩后的byte[]

    /**
     * @param bytes        原始的字符串对应的byte数组
     * @param huffmanCodes 生成的哈夫曼编码map
     * @return 字符串对应的压缩后的字节数组
     * 如： String str="i like like like java do you like a java";
     * =>  byte[] contentBytes=str.getBytes();
     * 返回字符串："1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
     * 对应的byte[]huffmanCodeBytes,即8位对应一个byte，放入到huffmanCodeBytes
     * 即huffmanCodeBytes[0] = 10101000(补码) =>byte[推导 10101000=> 10101000-1 => 10100111(反码) => 11011000]
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //利用huffmanCodes将bytes转成哈夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历bytes数组
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        System.out.println("原来的" + stringBuilder.toString());
        //1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
        // System.out.println(stringBuilder.toString());

        //将字符串转为byte[]
        int length;
        if (stringBuilder.length() % 8 == 0) {
            length = stringBuilder.length() / 8;
        } else {
            length = stringBuilder.length() / 8 + 1;
        }

        //创建存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[length];
        int index = 0;//记录是第一个byte
        for (int i = 0; i < stringBuilder.length(); i += 8) {//每8位对应一个byte
            String strByte;
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring(i);

            } else {

                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte转成一个byte放入到huffmanCodeBytes

            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;

        }
        return huffmanCodeBytes;

    }


    // 1.将Huffman编码表放在Map<Byte,String>中，如<97,100>
    private static Map<Byte, String> huffmanCodes = new HashMap<>();
    //2.生成哈夫曼编码表，需要去拼接路径，定义一个StringBuilding存储某个叶子节点的路径
    private static StringBuilder stringBuilder = new StringBuilder();

    /**
     * 方便调用，重载getCodes
     *
     * @param root
     * @return
     */
    private static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        //处理左子树
        getCodes(root.left, "0", stringBuilder);
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    /**
     * 将传入的node节点的所有叶子节点的哈夫曼编码得到，并放入到huffmanCodes集合
     *
     * @param node          传入节点
     * @param code          路径：左子节点是0，右子节点是1
     * @param stringBuilder 拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node != null) {
            //判断当前node是叶子节点还是非叶子节点
            if (node.data == null) {//非叶子节点
                //递归处理
                //向左
                getCodes(node.left, "0", stringBuilder1);
                //向右
                getCodes(node.right, "1", stringBuilder1);
            } else {
                //是叶子节点
                //找到了某个叶子节点的路径
                huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }

    }

    /**
     * @param bytes 接收字节数组
     * @return 返回List
     */
    private static List<Node> getNodes(byte[] bytes) {
        ArrayList<Node> nodes = new ArrayList<>();

        //存储每一个byte出现的次数
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        //把每一个键值对转成一个Node对象，并加入到nodes集合
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));

        }
        return nodes;
    }

    /**
     * 根据返回的node集合生成HuffmanTree
     *
     * @param nodes 节点集合
     * @return 哈夫曼树
     */
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            Node lnode = nodes.get(0);
            Node rnode = nodes.get(1);
            //新节点无数据，只有权值
            Node parentNode = new Node(null, lnode.weight + rnode.weight);
            parentNode.left = lnode;
            parentNode.right = rnode;

            nodes.remove(lnode);
            nodes.remove(rnode);

            nodes.add(parentNode);


        }
        return nodes.get(0);
    }

}

//创建Node，待数据和权值
class Node implements Comparable<Node> {
    Byte data;//存放数据本身，如'a': => 97 ' '=>32
    int weight; //权值，表示字符出现的次数
    Node left;
    Node right;


    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }


    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
}
